package com.asa.hutils;
/**
 * 	多项式相乘
 * @author Administrator
 *
 */
public class NTT2My {
	
	
	 
	public static void main(String[] args) {
		
		double a[] = {3,2,5};
		double b[] = {5,1,2};

		
		double[] c = C(a, b);
				

		for (int i = 0; i < c.length; i++) {
			
			System.out.println(c[i]);
			
		}

	}

	/**
	 * 两个多选式相乘，参数相运算，得出一个新的多项式的参数
	 * a和b两个多选式的长度要相同，即多项式的最大项次要一致，如果不一致，补0使其一致
	 * 
	 * @param a
	 * @param b
	 * @return
	 */
	public static double[] C(double[] a, double[] b) {
		double c[] = new double[a.length*2-1];
		
		double[][] asa =new double[a.length][b.length];
		
		//先将两个多项式相乘，得出一个矩阵
		for (int i = 0; i < asa.length; i++) {
			for (int j = 0; j < asa.length; j++) {
				asa[i][j] = a[i]*b[j];
			}
		}
		//所谓返回结果，就是矩阵的斜对角线上的值相加
		for (int i = 0; i < (c.length-1)/2; i++) {
			for (int j = 0; i-j >=0 ; j++) {
				c[i] += asa[j][i-j];
			}
		}
		
		for (int i = (c.length-1)/2; i < c.length; i++) {
			int index = i - (c.length-1)/2;
			
			for (int j = 0; j+index < asa.length; j++) {
//				System.out.println((index+j)+"    "+(asa.length-j-1));
				c[i] += asa[index+j][asa.length-j-1];
			}
			
		}
		return c;
	}
	
	
	
}
